class Solution(object):
    def maxPoints(self, points):
        m = len(points)
        n = len(points[0])
        st = points[0]
        st1 = [0] * n
        st2 = [0] * n
        st1[0] = st[0]
        st2[n - 1] = st[-1] - n + 1
        for i in range(1, n):
            st1[i] = max(st1[i - 1], st[i] + i)
            st2[n - 1 - i] = max(st2[n - i], st[n - 1 - i] - (n - 1 - i))
        for i in range(1, m):
            next_st = [0] * n
            for j in range(n):
                next_st[j] = max(points[i][j] - j + st1[j], points[i][j] + j + st2[j])
            st = next_st
            st1 = [0] * n
            st2 = [0] * n
            st1[0] = st[0]
            st2[n - 1] = st[-1] - n + 1
            for j in range(1, n):
                st1[j] = max(st1[j - 1], st[j] + j)
                st2[n - 1 - j] = max(st2[n - j], st[n - 1 - j] - (n - 1 - j))
        return max(st)


data = Solution()
points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]]
print(data.maxPoints(points))
